package com.ln.leetcode._1375;

import org.junit.Test;

/**
 * 二进制字符串前缀一致的次数
 * <p>
 * 给你一个长度为 n 、下标从 1 开始的二进制字符串，所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位（即，将 0 变为 1）。
 * 给你一个下标从 1 开始的整数数组 flips ，其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。
 * 二进制字符串 前缀一致 需满足：在第 i 步之后，在 闭 区间 [1, i] 内的所有位都是 1 ，而其他位都是 0 。
 * 返回二进制字符串在翻转过程中 前缀一致 的次数。
 * <p>
 * 示例 1：
 * 输入：flips = [3,2,4,1,5]
 * 输出：2
 * 解释：二进制字符串最开始是 "00000" 。
 * 执行第 1 步：字符串变为 "00100" ，不属于前缀一致的情况。
 * 执行第 2 步：字符串变为 "01100" ，不属于前缀一致的情况。
 * 执行第 3 步：字符串变为 "01110" ，不属于前缀一致的情况。
 * 执行第 4 步：字符串变为 "11110" ，属于前缀一致的情况。
 * 执行第 5 步：字符串变为 "11111" ，属于前缀一致的情况。
 * 在翻转过程中，前缀一致的次数为 2 ，所以返回 2 。
 * <p>
 * 示例 2：
 * 输入：flips = [4,1,2,3]
 * 输出：1
 * 解释：二进制字符串最开始是 "0000" 。
 * 执行第 1 步：字符串变为 "0001" ，不属于前缀一致的情况。
 * 执行第 2 步：字符串变为 "1001" ，不属于前缀一致的情况。
 * 执行第 3 步：字符串变为 "1101" ，不属于前缀一致的情况。
 * 执行第 4 步：字符串变为 "1111" ，属于前缀一致的情况。
 * 在翻转过程中，前缀一致的次数为 1 ，所以返回 1 。
 * <p>
 * 提示：
 * <p>
 * n == flips.length
 * 1 <= n <= 5 * 104
 * flips 是范围 [1, n] 中所有整数构成的一个排列
 */
public class Solution {

    public int numTimesAllBlue(int[] flips) {
        // flips 下标:  代表是第几次翻转
        // flips[下标]: 代表是当前要翻二进制数组的第几个数字
        // flip数组中的元素不会重复
        // 推出：flips 当下标是 x 的时候，在区间[1, x]中对应的二进制数字应该全部是1，那么flips中[1,x]对应的值也应该是 1 ~ x 这个区间值的集合
        // 那可以说明 flips在区间[1,x]的最大值应该是x
        // 当满足这个条件的时候，计数 + 1
        int count = 0;
        int max = Integer.MIN_VALUE;

        for (int i = 1; i <= flips.length; i++) {
            max = Math.max(flips[i - 1], max);
            if (max == i) {
                ++count;
            }
        }
        return count;
    }

    @Test
    public void test() {
        System.out.println(numTimesAllBlue(new int[]{3, 2, 4, 1, 5}));
        System.out.println(numTimesAllBlue(new int[]{4,1,2,3}));
    }

}
